package com.veal98.tree;

import com.veal98.bean.TreeNode;

public class TrimABinarySearchTree_669 {

    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }

        // 如果根节点都小于 low, 那么根节点的左孩子也会被全部剪去，所以修剪后的二叉树根节点必定出现在当前根节点的右孩子上
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }

        // 如果根节点都大于 high, 那么根节点的右孩子也会被全部剪去，所以修剪后的二叉树根节点必定出现在当前根节点的左孩子上
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }

        // 否则，我们需要修剪树的两边
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);

        return root;
    }

}
